package 背包问题;

/**
 * 最长公共子序列
 * leetcode url https://leetcode.cn/problems/longest-common-subsequence/
 */
public class Solution1143 {
    public static void main(String[] args) {
        String text1 = "psnw";
        String text2 = "vozsh";
        int i = longestCommonSubsequence1(text1, text2);
        System.out.println(i);

        int j = longestCommonSubsequence2(text1, text2);

        System.out.println(j);

    }

    public static int longestCommonSubsequence2(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        return dp(s1, s2, s1.length - 1, s2.length - 1);
    }

    public static int longestCommonSubsequence1(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        return process(s1, s2, s1.length - 1, s2.length - 1);
    }

    /**
     * i:s1[0~i]最长子序列
     * j:s2[0~j]最长子序列
     */
    public static int process(char[] s1, char[] s2, int i, int j) {
        //base
        if (i == 0 && j == 0) {
            //剩下0位置比较，如果一样就为1，不同就是0
            return s1[i] == s2[j] ? 1 : 0;
        }
        if (i == 0) {
            if (s1[i] == s2[j]) {
                //最后一个相同就代表最长是1
                return 1;
            } else {
                //j往右移动
                return process(s1, s2, i, j - 1);
            }
        } else if (j == 0) {
            if (s1[i] == s2[j]) {
                //最后一个相同就代表最长是1
                return 1;
            } else {
                //j往右移动
                return process(s1, s2, i - 1, j);
            }
        } else {
            //i 和 j都不是0位置结尾的
            //第一种可能性 i往前移动，找到了
            int p1 = process(s1, s2, i - 1, j);
            //第二种可能性 j往前移动，找到了
            int p2 = process(s1, s2, i, j - 1);
            //第三种 i和j在这个位置一样,找到了一种,继续往下找，加上，如果这个位置不一样，排除这个答案，返回0
            int p3 = s1[i] == s2[j] ? (1 + process(s1, s2, i - 1, j - 1)) : 0;
            return Math.max(p1, Math.max(p2, p3));
        }
    }

    /**
     * i:s1[0~i]最长子序列
     * j:s2[0~j]最长子序列
     */
    public static int dp(char[] s1, char[] s2, int i, int j) {
        //base
        int N = s1.length;
        int M = s2.length;

        int[][] dp = new int[N][M];
        //剩下0位置比较，如果一样就为1，不同就是0
        dp[0][0] = s1[0] == s2[0] ? 1 : 0;
        for (int rset = 1; rset < M; rset++) {
            if (s1[0] == s2[rset]) {
                dp[0][rset] = 1;
            } else {
                dp[0][rset] = dp[0][rset - 1];
            }
        }
        for (int index = 1; index < N; index++) {
            if (s1[index] == s2[0]) {
                dp[index][0] = 1;
            } else {
                dp[index][0] = dp[index - 1][0];
            }
        }
        for (int index = 1; index < N; index++) {
            for (int rset = 1; rset < M; rset++) {
                //i 和 j都不是0位置结尾的
                //第一种可能性 i往前移动，找到了
                int p1 = dp[index - 1][rset];
                //第二种可能性 j往前移动，找到了
                int p2 = dp[index][rset - 1];
                //第三种 i和j在这个位置一样,找到了一种,继续往下找，加上，如果这个位置不一样，排除这个答案，返回0
                int p3 = s1[index] == s2[rset] ? (1 + dp[index - 1][rset - 1]) : 0;
                int max = Math.max(p1, Math.max(p2, p3));
                dp[index][rset] = max;
            }
        }
        return dp[N - 1][M - 1];
    }
}
